package com.coder.algorithm.offer_2;

import java.util.Arrays;

/**
 * 连续子数组的最大和
 *
 * @author yuhushuan
 * @date 2020/6/25 09:26
 */
public class _42_1_GreatestSumOfSubArrays {

    private static Integer findGreatestSumOfSubArrays(int[] array) {
        if (array == null || array.length == 0) {
            return null;
        }
        int currentSum = array[0];
        int start = 0, end = 0;
        int from = 0;
        int greatestSum = currentSum;
        for (int i = 1; i < array.length; ++i) {
            // 数组重新开始
            if (currentSum <= 0) {
                currentSum = array[i];
                start = i;
            } else {
                currentSum += array[i];
            }
            if (currentSum > greatestSum) {
                greatestSum = currentSum;
                from = start;// start 可能记录多次，以上一次重新开始为准
                end = i;
            }
        }
        System.out.println(Arrays.toString(Arrays.copyOfRange(array, from, end + 1)));
        return greatestSum;
    }

    public static void main(String[] args) {
        print(new int[]{1, -2, 3, 10, -4, 7, 2, -5});
        print(new int[]{1, 2, 3});
        print(new int[]{-1, -2, -3, -4});
        print(null);
    }

    private static void print(int[] array) {
        System.out.println("数组：\n" + Arrays.toString(array));
        System.out.println("子数组和的最大值：\n" + findGreatestSumOfSubArrays(array));
        System.out.println();
    }
}
